import java.util.ArrayList;

//023. 非过剩数之和
//        如果一个数的所有真因子之和等于该数自身，那么这个数被称为完全数。
//        如果一个数的所有真因子之和小于该数自身，称其为不足数，如果大于该数自身，称其为过
//        剩数。
//        例如：
//        28 是一个完全数，因为 28 的所有真因子之和为 1 + 2 + 4 + 7 + 14 = 28
//        12 是一个过剩数，因为 12 的所有真因子之和为 1 + 2 + 3 + 4 + 6 = 16 > 12 自身
//        可以发现 12 是最小的过剩数，而 24 是最小的可以写为两个过剩数之和的数。
//        通过数学分析可以证明，所有大于 28123 的数都可以写成两个过剩数之和。
//        求所有无法写为两个过剩数之和的所有自然数的和。
//        答案：4179871
public class Week023 {
    public static boolean isAbundantNumber(int num) {
        return Week021.tureFactorSum(num) > num;
    }

    //程序运行时间：750889100ns
    static void run() {
        int n = 28123;
        int ans = 0;
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; ++i) {
            //每遇到一个过剩数就将其加入链表
            if (isAbundantNumber(i)) {
                list.add(i);
            }
            //接下来判断当前数能否分解为两个过剩数
            //遍历当前列表，如果另一个数也是过剩数，则符合要求
            boolean flag = true;
            for (Integer j : list) {
                if (isAbundantNumber(i - j)) {
                    flag = false;
                    break;
                }
            }
            //如果仍为true，则说明不能分解
            if (flag) {
                ans += i;
            }
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        run();
        System.out.println("\n程序运行时间：" + (System.nanoTime() - startTime) + "ns.");
    }
}
